package lanQiaoBei.tree;

import sjjg.tree.BinaryTree;

import java.io.Serializable;
import java.util.*;

public class TreeQuestion implements Serializable {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        node1.setLeft(node2);
        node1.setRight(node5);
        node2.setLeft(node3);
        node2.setRight(node4);
        node5.setRight(node6);
        node6.setRight(node7);
        node7.setRight(node8);
        System.out.println(lowestPublicAncestors(node1, node4, node3));
        treeSerializable(node1);
        printPaperCrease(1,7,true);
    }
    //打印纸条折痕
    public static void printPaperCrease(int i,int n,boolean flag){
        if(i>n){
            return;
        }
        printPaperCrease(i+1,n,true);
        System.out.print(i+(flag?"凹":"凸")+" ");
        printPaperCrease(i+1,n,false);
    }
    //序列化某棵树到字符串和反序列化字符串到某棵树(此处采用先序遍历的方式来进行序列化)
    public static void treeSerializable(TreeNode root) {
        if (root == null) return;
        //序列化
        String s = serializeTree(root);
        System.out.println(s);
        //反序列化
        LinkedList<String> queue = new LinkedList<>();
        String[] split = s.split(",");
        for (int i = 0; i < split.length; i++) {
            queue.addFirst(split[i]);
        }
        TreeNode head=reSerializeTree(queue);
        System.out.println(head);
        System.out.println(serializeTree(head));
    }

    private static TreeNode reSerializeTree( LinkedList<String> queue) {
        if(queue==null)return null;
        String s = queue.removeLast();
        TreeNode node=null;
        if(!"#".equals(s)){
            node=new TreeNode(Integer.parseInt(s));
        }else return node;
        node.setLeft(reSerializeTree(queue));
        node.setRight(reSerializeTree(queue));
        return node;
    }

    private static String serializeTree(TreeNode root) {
        if (root == null) {
            return "#,";
        }
        String s = root + ",";
        s += serializeTree(root.getLeft());
        s += serializeTree(root.getRight());
        return s;
    }

    //确定某个节点的后继节点 时间复杂度O(K)
    public static TreeNode aftNode(TreeNode root, TreeNode node) {
        if (root == null) return null;
        /*分两种情况*/
        //1.node无右子树
        if (node.getRight() == null) {
            return case1(node);
        } else {
            return case2(node);
        }
    }

    private static TreeNode case2(TreeNode node) {
        return null;
    }

    private static TreeNode case1(TreeNode node) {
        return null;
    }

    //最低公共祖先 给定两个节点（已知在同一棵树）找出两节点的最低公共祖先
    public static TreeNode lowestPublicAncestors(TreeNode root, TreeNode node1, TreeNode node2) {
        if (root == null) return null;
        //为每个节点生成一个map key为自己value为父节点
        HashMap<TreeNode, TreeNode> map = new HashMap<>();
        map.put(root, null);
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addFirst(root);
        while (!queue.isEmpty()) {
            TreeNode removeLast = queue.removeLast();
            TreeNode left = removeLast.getLeft();
            TreeNode right = removeLast.getRight();
            if (left != null) {
                queue.addFirst(left);
                map.put(left, removeLast);
            }
            if (right != null) {
                queue.addFirst(right);
                map.put(right, removeLast);
            }
        }
        HashSet<TreeNode> set = new HashSet<>();
        TreeNode temp = node1;
        while (temp != null) {
            set.add(temp);
            temp = map.get(temp);
        }
        temp = node2;
        while (temp != null) {
            if (set.contains(temp)) {
                return temp;
            }
            temp = map.get(temp);
        }
        return temp;
    }
}
